package com.lw.leetcode.stack.b;

import java.util.LinkedList;

/**
 * Created with IntelliJ IDEA.
 * stack
 * 1696. 跳跃游戏 VI
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/6 15:32
 */
public class MaxResult {

    public static void main(String[] args) {
        MaxResult test = new MaxResult();

        // 7
        int[] arr = {1, -1, -2, 4, -7, 3};
        int k = 2;

        // 17
//        int[] arr = {10,-5,-2,4,0,3};
//        int k = 3;

        // [1,-5,-20,4,-1,3,-6,-3], k = 2  0
//        int[] arr = {1,-5,-20,4,-1,3,-6,-3};
//        int k = 2;

        int i = test.maxResult(arr, k);
        System.out.println(i);
    }

    public int maxResult(int[] nums, int k) {
        LinkedList<Integer> list = new LinkedList<>();
        int length = nums.length;
        list.add(nums[0]);
        int index = Math.min(k + 1, length);
        for (int i = 1; i < index; i++) {
            int value = list.getFirst() + nums[i];
            while (!list.isEmpty()) {
                if (list.getLast() >= value) {
                    break;
                }
                list.pollLast();
            }
            list.add(value);
            nums[i] = value;
        }
        int st = 0;
        int end = index;
        while (end < length) {
            if (list.getFirst() == nums[st]) {
                list.pollFirst();
            }
            int value = list.getFirst() + nums[end];
            while (!list.isEmpty()) {
                if (list.getLast() >= value) {
                    break;
                }
                list.pollLast();
            }
            list.add(value);
            nums[end] = value;
            end++;
            st++;
        }
        return nums[length - 1];
    }
}
